package likou;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Tangxz
 * @email:1171702529@qq.com
 * @cate: 2020/11/04 15:24
 */
public class _57 {
    public static void main(String[] args) {
        System.out.println(insert(new int[][]{{1,5}},new int[]{6,8}));
        }
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        int min = newInterval[0];
        int max = newInterval[1];
        boolean p = true;//已经插入，则变为false
        boolean pp = true;//找到插入前面的一个数字
        List<int[]> daan = new ArrayList<>();
        for(int i=0;i<intervals.length;i++){
            if(p){
                if(intervals[i][1]<min){
                    daan.add(intervals[i]);
                }else {
                    if(pp){
                        min = intervals[i][0]>min?min:intervals[i][0];
                        pp=false;
                    }
                    if(max<intervals[i][0]){
                        daan.add(new int[]{min,max});
                        i--;
                        p=false;
                        continue;
                    }
                    if(max<=intervals[i][1]){
                        max = intervals[i][1];
                        p=false;
                        daan.add(new int[]{min,max});
                    }else if (i==intervals.length-1){
                        daan.add(new int[]{min,max});
                    }
                }
            }else{
                daan.add(intervals[i]);
            }
        }
        if (p){
            daan.add(new int[]{min,max});
        }
        int[][] daana = new int[daan.size()][2];
        for (int i=0;i<daan.size();i++){
            daana[i] = daan.get(i);
        }
        return daana;
    }

    /**
     * 时间超过100% 0ms
     * @param intervals
     * @param newInterval
     * @return
     */
    public int[][] insert2 (int[][] intervals, int[] newInterval) {

        int len = intervals.length;

        //如果原数组没有元素，或最后一个区间的终点小于新区间的起点，则将新区间添加到末尾
        if(len == 0 || newInterval[0] > intervals[len - 1][1]){
            int[][] ret = new int[len + 1][];
            ret[len] = newInterval;
            for(int i = 0; i < len; i++)
                ret[i] = intervals[i];
            return ret;
        }

        //如果第一个区间的起点大于新区间的终点，则将新区间添加到开头
        if(newInterval[1] < intervals[0][0]){
            int[][] ret = new int[len + 1][];
            ret[0] = newInterval;
            for(int i = 1; i < len + 1; i++)
                ret[i] = intervals[i - 1];
            return ret;
        }

        //否则，先找到两个特殊的下标：left和right，left左边的区间和right右边的区间肯定不与newInterval相交
        int left = 0, right = len - 1;
        while(intervals[left][1] < newInterval[0])
            left++;
        while(intervals[right][0] > newInterval[1])
            right--;

        //然后对从left到right的区间以及新区间进行合并，合并后的区间的起点分别为l和r，计算方式如下所示
        int l = Math.min(intervals[left][0], newInterval[0]);
        int r = Math.max(intervals[right][1], newInterval[1]);

        //依次把left左边的所有区间、合并后的区间、right右边的所有区间添加到新的数组中
        int[][] ret = new int[len - (right - left + 1) + 1][];
        int i = 0;
        while(i < left) {
            ret[i] = intervals[i];
            i++;
        }
        ret[i++] = new int[]{l, r};
        while(i < ret.length) {
            ret[i] = intervals[i - left + right];
            i++;
        }
        return ret;
    }
}
